The present invention relates generally to methods and apparatuses for arbitrating collisions due to simultaneously received data transmissions, and more particularly to a method and apparatus for arbitrating collisions due to simultaneously received data transmissions from multiple sensors.
RF identification tags are used in many applications, including but not limited to personnel identification, utility line markers, object tracking, etc. When communicating via wireless means (or a common bus), it is necessary to arbitrate a potential collision or contention that may arise from reading multiple units simultaneously. Each of these systems requires a main transmitting/receiving unit to distinguish from potentially multiple tags. Receiving multiple transmissions simultaneously requires the main transmitting/receiving unit to sort the transmission collisions using multiple re-interrogations (i.e., transmissions) and further process the received signals.
Utility lines are often marked with buried markers to help identify their locations. These buried markers can be detected using a radio frequency (RF) transmitter that interrogates the markers, which in turn transmit a reply signal. As the markers are buried relatively close to one another, the interrogating transmitter will often receive multiple signals simultaneously. When two signals are received simultaneously, this is known as a xe2x80x9ccollisionxe2x80x9d . Techniques for processing the received signals to avoid these collisions have been developed.
A basic concept in anti-collision transmitting/receiving systems is to design the system so that only one transmitter (e.g., a marker) responds at a time, thereby enabling the interrogating receiver to read a serial number of the replying transmitter without interference from other simultaneously transmitted signals. Signals that occupy the same time-frequency space create noise for a receiver attempting to receive the signals. Moreover, a similar signal having similar modulation and data rates creates coherent noise, in the presence of which it is particularly difficult to receive another signal.
Several techniques have been implemented in an attempt to overcome these problems. One technique assigns a unique time slot for each returning signal. This is known as time division multiple access (TDMA). This technique requires a large time slot for systems involving many possible signals. Employing this technique to avoid collisions in utility marker transmission/receiving system requires many assigned time slots, as the transmitter may not know which markers it will be interrogating in advance. Consequently, this technique becomes impractical in systems where many potential transmitters exist.
Another technique employs frequency division. In this protocol, called Frequency Division Multiple Access (FDMA), each signal is assigned a unique frequency. As with TDMA, FDMA requires many assigned frequencies, thereby making it impractical for use in interrogating utility markers given the large number of potential markers being interrogated.
Another technique employs code division. In this protocol, called Code Division Multiple Access (CDMA), each signal uses different code key. This technique suffers from the same disabilities as TDMA and FDMA for use in utility marking systems.
Another technique combines aspects of code division and time division. One example of such a technique is set forth in UK Patent GB 2 259 227, which discloses a combined TDMA/CDMA technique for processing multiple signals. Another example is set forth in U.S. Pat. No. 5,606,322 (Allen et al.), which discloses a method and apparatus for generating a pseudo-random code for use in avoiding RF collisions. However, this simply reduces the number of potential collisions, but does not solve the problem for large numbers of potential transmitters.
Another technique uses a random delay and code/frequency division. These techniques require a complex processor to generate the random delay. Moreover, collisions are still possible in such a system.
U.S. Pat. No. 4,471,345 (Barrett, Jr.) discloses a randomized tag to portal communication system. In this system, communication between portal units and identification tags is accomplished by continually radiating an interrogation signal consisting of a code pattern from each portal unit followed by a listening interval. Tags within range of such interrogation signal test the incoming signals for frequency, bit duration, bit rate, a preamble code and a facility identifying code. If the tag receives a valid signal to which it has been preprogrammed, such signal synchronizes and initiates a plurality of tag responses within a given overall response interval and with each response transmitted during randomly selected time slots.
Another technique broadcasts a signal directed only to specific markers. The one that includes the correct address is the only one that responds. This system requires advance knowledge of potential transmitters, which is not always available in utility marking systems.
U.S. Pat. No. 5,521,601 (Kandlur et al.) discloses a power efficient technique for multiple tag discrimination. This patent provides a tag identification system and method for identifying tags in the range of a reader station where the tags are divided into smaller groups and are identified one group at a time so as to save power by powering off the tags that are not in the group currently being identified. Each tag puts itself in a group by performing calculations from parameters stored in itself and from parameters received from the reader station. This technique requires many transmissions and a complex locator unit.
Another technique sorts by received power, which varies by distance to the receiver. This technique is unduly complex.
U.S. Pat. No. 5,266,925 (Vercellotti et al.) discloses an electronic identification tag interrogation method. In this method, the interrogation signal includes an address, which requests a response from every tag having an address greater than or equal to the address of the signal. If more than one address is received, the interrogation address is bisected and the interrogation signal is retransmitted. The interrogation signal is successively bisected until a single response is isolated.
U.S. Pat. No. 5,550,547 (Chan et al.) discloses a multiple item radio frequency tag identification protocol. This protocol uses a tree splitting algorithm applied to RF tagging. Essentially, using this protocol groups of tags are selected and deselected until no further RF collisions occur. A similar device is disclosed in U.S. Pat. No. 5,521,601, which powers groups on and off until no RF collisions occur. U.S. Pat. No. 5,673,037 also discloses a group selection/deselection technique.
U.S. Pat. No. 5,515,053 (Hecht et al.) discloses a transponder and data communication system in which the interrogating device transmits a coded signal containing wildcard entries in the code. If multiple signals are received, the interrogating device transmits another coded signal, but with fewer wildcards in the code. This process is repeated until only a single signal is received.
U.S. Pat. No. 3,860,922 (Wagner) discloses a device using a time dependent codeword to respond to an interrogation to avoid RF collisions.
PCT Patent Application No. WO 98/35327 discloses a random based non-interrogating technique for avoiding RF collisions from multiple RF tags.
Each of the above techniques are complicated to implement, thus decreasing the reliability of the marker, which is of critical importance for a device expected to last over fifty years. Moreover, the data rate employed in buried markers is relatively slow (approximately 125 Hz) to guarantee proper reception. Therefore, to attempt to assign a unique time slot to all markers requires a significant time delay.
The present invention is therefore directed to the problem of developing a method and apparatus for arbitrating between signals being transmitted from multiple RF identification tags buried along a utility route.
The present invention solves this problem by providing a primary communications channel and multiple secondary communications channels, such that each of the secondary communications channels is unique relative to the primary communications channel, and by commanding each of the radio-frequency markers to respond in one of the secondary communications channels based on a portion of a number available to each of the radio-frequency markers.